package 每日一题;

import java.util.ArrayList;
import java.util.List;

/**
 * 22. 括号生成
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 示例 2：
 * <p>
 * 输入：n = 1
 * 输出：["()"]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= n <= 8
 */
public class D230328_T0022 {

    public static void main(String[] args) {
        D230328_T0022 d230328_t0022 = new D230328_T0022();
        List<String> strings = d230328_t0022.generateParenthesis(3);

    }

    //使用dfs 深度递归遍历
    //左括号的使用数量 严格大于右括号的使用数量 才不会出现 "(()))(()" 这种情况

    public List<String> generateParenthesis(int n) {
        ArrayList<String> res = new ArrayList<>();
        int left = n;
        int right = n;

        if (n == 0 || n < 0) {
            return res;
        }

        dfs("", left, right, res);

        return res;


    }

    /**
     * @param s     遍历到当前节点生成的字符串
     * @param left  左括号剩余数量
     * @param right 右括号剩余数量
     * @param res   结果集
     */
    private void dfs(String s, int left, int right, ArrayList<String> res) {

        if (left == 0 && right == 0) {
            res.add(s);
            return;
        }

        if (right < 0 || left < 0) {
            return;
        }
        if (right < left) {
            return;
        }

        if (right > left) {

            dfs(s + "(", left - 1, right, res);
            dfs(s + ")", left, right - 1, res);
        }

        if (right == left) {
            dfs(s + "(", left - 1, right, res);
        }

    }


}
